package com.lft.search02.binary_search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 */
public class BinarySearch {
	public static void main(String[] args) {
		// int[] a = {1, 3, 6, 8, 9, 11, 15, 18, 20, 28, 93};
		// int[] a = {1, 3, 6, 8, 9, 11, 15, 15, 15, 15, 15, 18, 20, 28, 93};
		int[] a = new int[100];
		for (int i = 0; i < 100; i++) {
			a[i] = i + 1;
		}
		
		// int index = binarySearch(a, 0, a.length - 1, 15);
		List<Integer> list = binarySearch2(a, 0, a.length - 1, 1);
		if (list.size() == 0) {
			System.out.println("没有找到");
		} else {
			System.out.println("找到的索引为：" + list);
		}
	}
	
	/**
	 * @param a     原始数组
	 * @param left  左边的索引
	 * @param right 右边的索引
	 * @param value 要查找的值
	 */
	public static int binarySearch(int[] a, int left, int right, int value) {
		if (left > right || value < a[0] || value > a[a.length - 1]) {
			return -1;
		}
		int mid = (left + right) / 2;
		int midValue = a[mid];
		
		if (value < midValue) {
			return binarySearch(a, left, mid - 1, value);
		} else if (value > midValue) {
			return binarySearch(a, mid + 1, right, value);
		} else {
			return mid;
		}
	}
	
	/**
	 * 课后思考题： {1,8, 10, 89, 1000, 1000，1234}
	 * 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.
	 * <p>
	 * 思路分析：
	 * 1. 在找到 mid 值时，不要马上返回
	 * 2. 向 mid 索引值的左边扫描，将所有满足 重复的元素，下标，加入到集合中。
	 * 3. 向 mid 索引值的右边扫描，将所有满足 重复的元素，下标，加入到集合中。
	 * 4. 将集合返回
	 * @param a
	 * @param left
	 * @param right
	 * @param value
	 * @return
	 */
	public static List<Integer> binarySearch2(int[] a, int left, int right, int value) {
		System.out.println("====");
		if (left > right || value < a[0] || value > a[a.length - 1]) {
			return new ArrayList<Integer>();
		}
		
		int mid = (left + right) / 2;
		int midValue = a[mid];
		
		if (value < midValue) {
			return binarySearch2(a, left, mid - 1, value);
		} else if (value > midValue) {
			return binarySearch2(a, mid + 1, right, value);
		} else {
			
			List list = new ArrayList();
			int temp = mid - 1;
			while (true) {
				if (temp < 0 || a[temp] != value) {
					break;
				}
				list.add(temp);
				temp--;
			}
			list.add(mid);
			temp = mid + 1;
			while (true) {
				if (temp > a.length || a[temp] != value) {
					break;
				}
				list.add(temp);
				temp++;
			}
			return list;
		}
		
	}
}
